6.857 computer and network security october 22, 2002 lecture notes 13 : palladium, zero knowledge lecturer: ron rivest scribe: baratz/gavacs/sen/sudan [these are the initial scribe notes. the nal version will appear with updated gures. namely, the gures will have larger fonts.] 1 outline - palladium discussion - zero knowledge proofs 2 palladium discussion prof. rivest : what did people like / dislike about palladium? student : i think it's interesting to think about the various other organizations that are a ecting palladium, like hollywood, etc. student : i don't think palladium is going to
y. they haven't really come up with a killer-app and the cost is going to be too high. what is the killer app? movie and music distribution? prof. rivest : could movie distribution be the killer app? that really seems to be their driving motivation. student : it seems as though the only way they can justify this initiative is if they envision pcs becoming the center of a home theater system. using pcs to control dvd players, tvs, etc. prof. rivest : a very useful way of thinking about it is as a virtual embedded set top box. student : how can they use this system for drm if it isn't physically tamper-resistant? maybe due to the dmca it would be illegal to install dual-ported memory. hardware attacks could probably be carried out for hundreds of dollars or less. a movie could be extracted and then distributed. prof. rivest : besides drm, what could this be used for? student : possibly subscription services, software licensing, or piracy control. student : the whole tcpa framework provides a lot of functionality to enterprises. student : it seems as though the right-hand side of palladium won't really be used that much and isn't robust enough to run complete applications like word, etc. prof. rivest : this reminds me of how we drew the distinction between user and kernel space, and then with microsoft operating systems and plug-and-play people have been able to insert drivers, etc. into kernel space. now all they've done is draw another line and are daring outsiders to cross that line. after a while all sorts of code will have found its way into the palladium zone and then what do we do? draw another line and make palladium 2? 0 may be freely reproduced for educational or personal use. 1
2 3 zero-knowledge proofs prof. rivest : any other questions about palladium or its applications. how many of you think palladium isn't going to
y? a couple dozen people raise their hands. why isn't it going to
y? student : not enough perceived bene t to the user. i don't think the end user desire exists. lack of motivation. maybe government agencies and enterprises will be interested. prof. rivest : it will be interesting to see how this rolls out: so one of the things palladium does is burn in keys. figure 1: palladium model. the keys shown here in the nexus are actually in a separate chip called the ssc. pk represents the machine's identity. we don't necessarily want to sign everything with pk, since this will reveal machine-speci c information that could compromise our privacy. one thing we could do is generate a new pk1 and send pk, cert(pk), and pk1 to a certi cate authority (ca). the ca would then return cert(pk1). basically the certi cate says that the key belongs to a palladium machine, but doesn't say which one. we have created an alias and provided anonymity. the problem with this architecture is that the ca knows all the mappings from pk to pk1. this may be what you want, but if not, what you might really be after is a way to convince the ca that you have a palladium machine with a pk/sk and a certi cate, without actually revealing those items. how can this be done? enter zero-knowledge (zk) proofs: 3 zero-knowledge proofs in a zero-knowledge (zk) proof, you are basically trying to convince someone that you know some- thing without telling them what it is, such as the message m corresponding to a known public ciphertext c .
3.1 the general set-up 3 3.1 the general set-up p = prover v = veri er wants to prove he knows m wants to learn if p knows m w =witness ! x =random challenge y =response ! test ( c; w; x; y ). accept if ok, reject otherwise. we want the protocol to satisfy the following properties: 1. if p does know m , then v always accepts. (completeness) 2. if p does not know m , then p is unlikely to convince v . (soundness) soundness may be shown by demonstrating that if p is prepared to respond to several di erent challenges (for the same witness), then in fact p must know (or must be able to easily compute) m . we would also like to have that the protocol be zero-knowledge : the veri er learns nothing (zero), aside from the fact that p knows m . 3.2 3-colorability example we have an undirected graph with 5 vertices. can we color the vertices with three colors so that no two adjacent vertices have the same color? a given graph may have many possible colorings, only one coloring, or no colorings at all. suppose i have a graph with a million vertices and i tell you i know how to color it using 3 colors. i want to convince you that the graph is 3-colorable without telling you what the coloring is. is there some way i can convince a remote computer, the skeptic, that i know how to do the coloring without saying what the coloring is? consider the following exchange between the prover (you, the person who knows the 3-coloring) and the veri er (the remote computer you are trying to convince): for a given graph coloring, there are 6 di erent permutations of the coloring possible: rgb, rbg, brg, bgr, gbr, grb. that is, you take one coloring and just permute the color assignments (e.g. from rgb to rbg, all vertices that are r are still r, all vertices that are g are now b, etc.). again, this is just for one coloring that the prover picks. we can represent each permutation as a sheet of paper with the graph and coloring on it (see figure 4 below). [figure 4: representation of the 6 permutations of a given graph 3-coloring] do t times: prover: picks a sheet (graph with a coloring permutation) from a random pile (veri er doesn't know which pile prover picks) and puts it on the table covering up vertices with little stickies
4 3 zero-knowledge proofs figure 2: 3-coloring of an undirected graph with 5 vertices veri er: points to 2 adjacent vertices prover: removes stickies from the two selected vertices veri er: checks that two vertices have di erent colors (if not ) not ok ) output: ok this algorithm is polynomial in the size of the graph (v + e, where v is the set of vertices and e is the set of edges), assuming that t is bounded by a polynomial in j v j and j e j . what are the properties of this protocol? - completeness: if prover knows coloring, veri er always accepts - soundness: if prover doesn't know coloring, he will be caught with signi cant probability. o prob(veri er picks \bad edge") 1 j e j o prob(veri er picks \good edge") 1 1 j e j o so in t trials: prob (bad prover escapes detection) (1 1 j e j ) t e t j e j since e x 1 + x , this probability is bounded above by e t= j e j , which for t = j e j 20 is less than e 20 . q : if t is j e j 20 , aren't you exposing more than the number of edges in the graph? a : yes, but each time you expose an edge it could be from any of the 6 piles (the veri er doesn't know which pile the user picks) we will try to show that the veri er doesn't learn anything if this scheme is followed. the idea is that there is no correlation between pairs of colors revealed by each edge. q : why can't the prover cheat by just showing di erent colors for each pair of vertices requested by the veri er (that is, choosing the vertex colors right before revealing them and that way guaranteeing
3.3 proof using discrete logs 5 figure 3: high-level overview of exchange between prover and veri er that the coloring works)? a : the prover actually commits to a coloring before hand, so all he can do is remove the stickies and expose the vertex colors. q : does the prover need to know all possible colorings in this scheme? a : no (look above). the prover picks one coloring and just permutes the color assignments (so the coloring scheme actually remains the same). our informal proof of \zero-knowledge": the veri er gets a transcript of his conversation with the prover and nothing more (transcript embodies all information obtained by the veri er). we are assuming that the prover takes the same amount of time to respond to each challenge (so, for instance, the veri er can't learn anything extra based on the time taken for the prover to respond). the information we get from this protocol is: this distribution of transcripts can be simulated by veri er, without prover's help. 3.3 proof using discrete logs we now give another illustration of a zero-knowledge protocol. the goal of this protocol is for the prover to convince the veri er that he knows the discrete logarithm x of a public value (his public key) y . global public parameters: prime p , prime q dividing p 1, g of order q . public key of prover: y = g x mod p
6 3 zero-knowledge proofs figure 4: representation of the 6 permutations of a given graph 3-coloring private key of prover: x s.t. 0 x < q do t times: - prover: picks k 2 z q , sends u = g k mod p - veri er: computes b 2 r f 0 ; 1 g , sends b to prover - prover: sends l = k + bx mod q - veri er: computes u y b = g l mod p note that the prover can always succeed in each round with probability 1 = 2, by guessing b rst, then setting u = g l =y b . this protocol is sound and complete. the veri er will always accept an honest prover's proof, and a cheating prover will be caught with signi cant probability in each round. now the claim is that the protocol is zk. we can play this game all day long and there is no way the veri er will learn any information about x . the veri er just gets a huge list of u , b , and l during each iteration, but the claim again is that this tells us nothing about x . to demonstrate our claim, we can generate transcripts (on our own) with the proper distribution: - pick b 2 r f 0 ; 1 g - pick l 2 r z q - pick u = g l =y b mod p
3.4 applying zk to palladium 7 figure 5: information gained by veri er after t iterations of above communication protocol this gives us a triple ( u; b; l ) which we claim is indistinguishable from the actual transcript generated by the prover-veri er protocol above. (this is for an honest veri er. if the veri er actually generates b in some other way, such as making it depend on u , then this simulation needs to be modi ed by ltering the output appropriately. details omitted in this class. but in any case, the veri er can simulate the distribution on transcripts, which proves that the protocol is zk.) a much more general and wonderful result is also known. indeed, for any polynomial time program p , i can convince you (in zero knowledge) that i know x , y , z , etc. such that p ( x; y; z; : : : ) = true, where p () is some polynomial time program. clearly, this is quite a powerful cryptographic tool. 3.4 applying zk to palladium the secure support component (ssc) of palladium is a hardware module that can perform certain cryptographic operations as well as securely store one or more cryptographic keys. it has the public- private key pair ( sk 0 , p k 0 ) that is burned into the machine (as we mentioned earlier). i want to convince a ca in zero-knowledge that i know sk 0 , p k 0 , c 0 , sk 1 such that: - sk 0 is the secret key for p k 0 - c 0 is a certi cate from dell on p k 0 - sk 1 is the secret key for p k 1 (ca knows p k 1 ) at this point if the ca is convinced it returns cert ( p k 1 ). thus the ca can certify p k 1 without knowing how to link it to the original public key p k burnt into the ssc by the manufacturer.
|
